package com.zheng.coderepo.algorithm;

import org.junit.Assert;
import org.junit.Test;

/**
 * 计算两个数的最大公约数和最小公倍数.
 * Created by zcz on 2018/5/21.
 */
public class GcdAndLcm {

    /**
     * 辗转相除法，又称欧几里得算法。是求最大公约数的一种方法。
     * 算法原理：若a除以b的余数为r , 则有 (a , b) = ( b ,r )  （(a,b)表示a和b的最大公约数）
     * @param a
     * @param b
     * @return
     */
    public int gcd01(int a, int b) {
        int max = Math.max(a, b);
        int min = Math.min(a, b);
        int r = max % min;
        if (r == 0) {
            return min;
        } else {
            return gcd01(min, r);
        }
    }

    public int gcd02(int a, int b) {
        int max = Math.max(a, b);
        int min = Math.min(a, b);
        while (max % min != 0) {
            int tmp = max % min;
            max = min;
            min = tmp;
        }
        return min;
    }

    /**
     * 最小公倍数=a*b/gcd(a,b)
     * @param a
     * @param b
     * @return
     */
    public int lcm01(int a, int b) {
        return (a * b) / gcd01(a, b);
    }

    @Test
    public void testGcd() {
        Assert.assertTrue(gcd01(252, 105) == 21);
        Assert.assertTrue(gcd02(252, 105) == 21);
    }

    @Test
    public void testLcm() {
        Assert.assertTrue(lcm01(6, 5) == 30);
        Assert.assertTrue(lcm01(60, 24) == 120);

    }
}
